networkedlifeq21fandomcom-20200213-history
How To Control Airport Congestion ? by Tanmayee Tankasali, Thiriveedhi Srinidhi Keshav
A''' '''SHORT ANSWER Airport surface congestion is one of the most important factors of delays at the airport. There are several reasons that cause congestions. Air traffic operations have significantly increased worldwide while airport capacity has been lagging. Over the past decades these airports have been facing increasing demand, which includes growth of airline operations and globalization of the economy. In the year 1986 New-York Times’ magazine had estimated that domestic airport ground delays was around 2000 hours/day. Since the deregulation of airline industry which has increased form 17% to 36%, it negatively affected air transportation demand. The Federal Aviation Administration (FAA), estimates that annually the departure taxi delay is around 48 million minutes. Incoming aircraft at an airport requires service at a system consisting of three stations: a landing runway, a gate, and a departure runway. The system has following characteristics to make it unsuitable for traditional analysis: 1.Time variation in arrival rate – all hub airports are subjected to a high time varying rate of demand. 2.Weather dependent of service rate – the service rate depends on runway configuration and number of landings and take-offs. The factors that affect weather conditions are cloud ceiling, visibility of the run way, wind direction and the speed. 3.Interdependence of service times – this deals with the amount of separation between landing and take-off, for ex, the required rate of separation should be six nautical miles when a heavy aircraft is followed by a small aircraft, and 3 nautical miles of separation when a small aircraft is followed by a heavy aircraft. From the figure we can observe four kinds of delays. Taxi-in delay – it is the time taken by the flight to reach its gate after touch down. Taxi-out delay – the time required by the airplane from the gate to the runway Departure delay – it is the length of the time taken by a flight from the runway till it takes-off Arrival delay – is the length of time required by a flight to touch down To overcome the above factors, a Markov/Semi-Markov prediction model algorithm is developed with two processes namely demand process and service process. An airport congestion control strategy in its simplest form would be a state-dependent pushback policy aimed at reducing surface congestion also known as departure process model. The objective of control strategy is to minimize the taxi-out delays at the airport. ATC suggested that the push-back rate is validated at the start of each epoch. The length of the time period ∆''t'' should be equal to the delay between expected times from the gate to the departure queue. In the given time interval, the flights released from gate are assumed to reach the departure queue in the next time period. A''' '''LONG ANSWER DEMAND PROCESS The airports operating day is modelled as consisting of K discrete time intervals, indexed by k'' = 1,2,….,K, each of length ∆''t. For interval k'', the number of aircraft demanding to land, λ''k, is a known constant. Considering the airport as a queuing system all the airport operations can be modelled. Runway system provides the service, and is the main bottleneck of operations at congested airports. Departing airplanes, physically queue on the ground, mainly on the taxiways (runways); arriving airplanes queue in the terminal airspace or in the en route airspace. A typical ariival and departure process for a given airplane at a given airport is described in figure 3: the airplane arrives first into the queuing system when it is ready to touch down, and the leave the queuing system when it actually lands. After landing the aircraft goes through another delay called the Taxi-in delay before it reaches its respective gate. Aircraft goes through a similar process when it departs from the gate. The time spent by the aircrafts while undergoing this process are the arrival and departure delays. A day’s operations are divided into 96 slots of 15-minute periods each. The inputs to the model are: Demand profile: it is the number of scheduled flights at time slot of the day. It include both departures and arrivals. Capacity profile: is the capacity of the airport at each period of the day. As a function of demand and capacity profiles, this model computes the delays at each period of the day. The demand procedure is displayed as a Poisson procedure with time-differing intensity. This gives a numerical representation of the times when airplane request utilization of a runway, either for a departure or for an arrival. The stochasticity of this procedure is propelled by the instability with respect to the times at which air ship are prepared to take-off or to land and join the line. To be sure, these circumstances are controlled by a few components which are to a great extent indeterminate and variable, including carrier operations, the operations in traveller structures, on-time execution at different air terminals, and so forth. MARKOV/SEMI-MARKOV ALGORITHM MODEL ' A stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event '' pij (m) = Pr''((i,'' m'') --> ''(j, 1)) Pr[T''i'' = m'' | T''i ≥ m''] pij'' j''≠''I '' pij'' (m) = Pr''((i,'' m'') --> ''(i, m + ''1)) = Pr[T''i = m + ''1 | T''i ≥ m''] '' where, '' m = time for which capacity has been in effect '' '' i = capacity '' '' pij = probability of the state '' '' Ti = arbitrary discrete distribution '' '''SERVICE PROCESS Landing capacity at the airport during given interval j ''is given by ''µ''1 < ''µ''2 < ''µ''3 ….. < ''µ''S Discrete distribution with probability mass function is given by '' Pi(k) = Pr{Ti ''= ''k} where, µ''S ''service rate of system S. Pi(k) probability of capacity µ for k intervals of length ∆t. Pr random holding time for a given state. Ti '' arbitrary discreet distribution. The service rate ''µ(t) is defined as the number of departing aircraft from the runway modeled per 15-minute interval. Three following assumptions are made in the service process: 1. The service rate is assumed to follow a time-dependent (dynamic) Erlang Distribution. 2. There is ﬁnite queuing space for the departing aircraft to wait in. 3. Aircraft in the departure queue are served on basis of first come first serve (FCFS). The service time, given by an airport is defined as the airport capacity and is modelled as an Erlang random variable. The time between consecutive activities is assumed to follow an Erlang distribution with a fixed parameter k''. When ''k ''=1, we obtain the results in an exponential distribution. It’s said the service process is a Poisson process if the results are in exponential distribution; when ''k = ∞, the process is deterministic. The runway queueing system is modeled as a discrete-time Markov Chain. Service completion of an Erlang process with shape k'' and rate ''kµ is represented with k'' stages of exponentially distributed random variables with rate ''kµ. Each such stage is called a stage-of-work. State q'' of the Markov chain denotes that there are ''q stages-of-work to be completed at the runway, i.e., there are min(1,q'') aircraft in service and max(⌈(''q − k)/''k''⌉,0) aircraft in the departure queue. The notation used in this section is as follows: • l'': Index of each aircraft. • ∆: Duration of each time window, set to 15 minutes. • ''i: Index of each time window. • (ki,kiµi): Shape and rate parameters of Erlang service time distribution in time period'' i''. • C'': Queuing space of the queuing system, measured in number of aircraft. • ''Ql: Stages-of-work to be completed immediately after lth aircraft’s arrival to empty the system. • pQl(j) : Probability that Ql takes the value'' j''. • cj: Inter-arrival time at the runway between the (j −1)th''and ''jth aircraft. • Cl ''= : Time of arrival of the ''lth aircraft. • Sl: Total time that aircraft l'' spends in the queuing system, including time-in-service. • ''Dl: Queuing delay that aircraft l'' experiences. • ''Z0: Number of aircraft in queue at the beginning of the ﬁrst time window. • f''ν(''x),F''ν(''x): P.D.F., C.D.F of r.v. X'' drawn from Poisson distribution with parameter ν''. STATIC SERVICE TIME DISTRIBUTION ' The runway service process is assumed to be static described by a single Erlang distribution with parameters ''(k,kµ). The system is observed at the epochs of arrival, Cl, of each aircraft l''. The figure shown is an example of the state of the Markov chain. Assume that there are exactly 3 stages-of-work to be completed before the arrival of ''lth aircraft in the system. Upon the arrival of lth aircraft, 2 stages-of-work are added and the system takes transitions to state 5. The Erlang distribution is taken with shape 2. plij is deﬁned as the probability that there are i'' stages-of-work to be completed immediately after the arrival of the lth'' aircraft, given that there were j'' stages-of-work to be completed immediately after the arrival of the ''(l−1)th aircraft. Then, since the system evolves as a Poisson process in time cl: In the above equation, an event is deﬁned as the completion of a stage-of-work in the Markov chain of the system. The time between each pair of consecutive events has an exponential distribution with parameter (kµ). z → number of events during time cl; then z = j +k − i''. '' Up to'' j'' stages-of-work can be completed in time cl, so 0 ≤ z ≤ j. Since the arrival of the lth aircraft adds k'' stages-of-work, ''i ≥ k. The probability of z < j'' events is therefore given by the Poisson distribution with parameter (kµcl). The constraint that z ≤ j implies that the probability of'' emptying the queuing system is equal to one minus the probability of having 0,1,...,j −1 events. P(ν) is a stochastic matrix, as its columns sum up to 1 for all k'' and ''ν. Given the probabilistic state of the Markov chain described by p''Ql'' at the time of arrival, the moments of the queuing time of each aircraft can be calculated assuming a static service process, an Erlang distribution with parameters (k,kµ). The first moment is given by: The second moment is given by: The mean and variance of the queuing delay can be calculated similarly by subtracting the service time for the lth aircraft, that is, k stages-of-work, and then calculating the moments. 'DYNAMIC SERVICE TIME DISTRIBUTION ' The state space of the queuing system can change in the dynamic case. p''Ql'' = P''(''vi) p''Ql-1 '' Given two runway throughput distributions, with shapes k1 and k2, where k1 ≠ k2, the state-space of the Markov chain corresponding to the ﬁrst distribution is {0,1,...,k1C} and the second is {0,1,...,k2C}. Transitioning from the ﬁrst throughput distribution to the second will require mapping the probabilities of states {0,1,...,k1 ·C''} to those of {0,1,...,k2 ·C}.'' 'DEVELOPMENT OF CONTROL STRATEGY ' The maximum throughput of a generic network, it is necessary to ﬁnd the maximum throughput of a network containing a single link l''. Initially, let the link be capable of accommodating an inﬁnite number of aircraft. This link is operating in deterministic steady state, with the taxi time of each aircraft being equal to its expectation value. Aircraft are distributed regularly along its length, with each departure from the link occurring after a ﬁxed time interval, and each arrival to the link happening at the same instant. If ζ''l is the arrival rate to the link, under this assumption, a new arrival occurs every (1/ζ''l'') seconds. The average travel time for each link is modeled as, where nl and λl '' → Erlang order variable with order and rate ''µl → '' stop time duration → stopping probability on each link '' Ns,l '' ''→ Number of stops '''DEPARTURE PROCESS MODEL At any time t, the state Nt of the departure process consists of the number of aircraft traveling from the gates to the departure queue (Gt) and the number of aircraft in the departure queue(Dt): Nt = (Gt, D''t)'' Wt ''= ''Gt +'' Dt'' Wt → total number of aircraft taxiing out PUSHBACK PROCESS At each epoch, the pushback rate, λ A = {0,1,……, λ''max } ''where '' λ = number of pushbacks per ∆ minutes In contrast to typical dynamic queuing control problems in which the decision maker sets the arrival rate into a facility, in this case, when setting a pushback rate at epoch ''τ, the decision maker authorizes λ aircraft to push back in that time period. Departure runway queuing system resembles a M(t)/Ek/1 system of queuing space C'', with the additional constraint of arrivals during the (τ,τ'' +∆] time interval. We denote it (M(t)|)/Ek/1. Assuming that at epoch τ'', aircraft are taxiing out, the probability density function g of the ''rth arrival at the departure runway at time t'' is: A state of the Markov chain (''r,q) implies that there are r'' aircraft that have been traveling to the runway since the start of that epoch, and there are q'' stages of work to be completed at the departure runway server. In other words, there are min (1,q) aircraft in service and max(⌈(q−k)/''k''⌉,0) aircraft in the departure queue. In the above figure, at epoch 0, the Markov chain is at the bottom level state (R0, Q0), namely, R0 aircraft traveling to the departure runway and Q0 stages of work to be completed. By the end of epoch ∆, all R0 aircraft will have reached the departure queue, and the Markov chain will be at the top level (0 aircraft traveling). Let Pr,q(t) denote the probability that the queuing system is in state (r, q) at time t''. The state probabilities ''P0,0(∆), P0,1(∆),···P0,kC(∆) describe the state of the queuing system at the end of the time interval ∆, and can be determined by considering the possible transitions of the Markov chain. The probability of the queuing system state at time ∆ being i'' = ''Q∆ is given by Q∆ = f (R0, Q0) with pq(i)(R0, Q0'') = P0,i(∆) ''for 0 ≤ i ≤ kC ⇒ pq(R0, Q0) = P0(∆) [''P0,0(∆), P0,1(∆),···P0,kC(∆)]′'' SYSTEM DYNAMICS At epoch τ'', there are aircraft traveling to the departure runway, stages of work left in the queue, and the decision maker selects a pushback rate λτ.'' The queuing system therefore evolves according to the following equation: (Rτ+∆,'' Qτ+∆'') = (λ''τ,f''(Rτ,Qτ)) The state St of the queuing system maps to the state Nt of the departure process as follows: Where Vt = Number of aircraft that pushed back between the start of the time period in which t'' lies, and time ''t. The aircraft reach the runway during the time interval (τ, τ+] and aircraft at t> τ+∆ ''. Then, Equation (A) becomes The above equation is to maintain Markov Property '''EXAMPLES' Pushback Control Policy at BOS Consider the average taxi-out time at BOS is 12.6 minutes. There is an added delay due to taxiway congestion, which is 1-2 minutes under moderate trafﬁc conditions. 15 minutes is therefore a suitable choice of time-window at BOS. The set of permissible policies is deﬁned as = {0,1,...,. is estimated to be 15 aircraft/15 min, and the queuing system capacity (C'') is estimated to be 30 at BOS. The cost of underutilizing the runway, c(0), is chosen to be equal to the cost of a queue of 25 departures. The optimal policy is given by The optimal pushback rate = 0, when ''W τ '' ≥ 23 The optimal pushback rate > 13 when ''W τ ≤ 13 These conditional forecasts shown above are incorporated into the algorithm as follows: (1) At epoch τ'', the conditional throughput for the time window (τ, τ''+∆] is predicted from the regression tree, using the expected number of arrivals (A) and the number of props taxiing out (P). (2) The expected takeoff rate in the time window (τ, τ''+∆] and queue length at τ''+∆ are calculated using a Markov queuing model with parameters ﬁtted to the throughput forecast from the previous step. Delay Calculation The table below shows the example of a flight by ATC management control. Key: dept_time: actual gate departure time - 4:42:00 AM arr_time: actual gate arrival time - 10:23:00 AM fs_dept_time: scheduled gate departure time - 3:05:00 AM fs_arr_time: scheduled gate arrival time - 9:16:00 AM out_time: time aircraft leaves gate or parking position (gate out time) - 4:30:00 AM off_time: time aircraft takes off (wheels-off time) - 4:41:00 AM on_time: time aircraft touches down (wheels-on time) - 10:19:00 AM in_time: time aircraft arrives at gate or parking position (gate in time) - 10:23:00 AM The calculations for the delay are calculated as follows: (1) Actual departure delay''' = gate departure time – taxi_time) – scheduled gate departure time (2) Actual departure delay for flight UAL225 = – (off_time – out_time) – fs_dept_time = – (4:41:00AM – 4:30:00AM) – 3:05:00AM = 1:24:00 hrs (3) Actual arrival delay for flight UAL225''' = time – (in time – on time) – fs_arr_time = – (10:23:00AM – 10:19:00AM) – 9:16:00AM = 1:03:00 hrs IMPLEMENTATIONS AND RESULTS A key objective of the ﬁeld-test was to maintain pressure on the departure runways, while limiting surface congestion. Runway utilization was shown to not be adversely impacted by the control strategy by checking that there was always at least one aircraft in the runway queue during the demo periods. Fig. 9 depicts the events of the demo period, divided into 15-minute () windows. The top plot shows the number of aircraft that called for pushback the number of pushbacks that were cleared, and the resulting number of jet aircraft actively taxiing out. It basically shows the demand process for pushback. As the number of jet aircraft taxiing-out exceeds 14, gate-holds are initiated in order to regulate the trafﬁc to the desired state. For this conﬁguration, the desired state is 13-14 aircraft on the surface. The middle plot shows the predicted and measured throughput. The airport stays in the desired state despite the high variance of the departure throughput and the rounding-off of the recommended pushback rates. Finally, the bottom plot shows the average taxi-out times and gate-holding times for aircraft that pushed back in each time interval. By maintaining runway utilization, it is reasonable to expect that gate-hold times translate to taxi-out time reduction. For banks 1 and 3, the second carrier in the order (American for bank 1, Delta for bank 3) has the higher delays, while for banks 2 and 4, American is higher despite coming first in the order. While this evidence is mixed, note that since in the two early morning banks there is still some separation between the two carriers, the effect on the Delta would be mitigated somewhat, while American's higher traffic would tend to increase its own queueing delays. In the case where the two carriers' banks actually overlap significantly (bank 3), Delta shows higher average delays, even with less traffic. Moreover, American's delays are only significantly higher than Delta's in the one case where it is scheduled second (bank 1). Overall, the data suggest that schedule position does play a role. CONCLUSION A model has been developed to solve congestion at hub airports This algorithm effectively adapts to changes in airport departure capacity Pushback control strategy achieves high runway utilization FURTHER RESEARCH Model validation Improvements and implementations Further application areas Redesign of airline networks REFERENCES 1 Peterson, M. D. (1992). “Models and algorithms for transient queueing congestion in airline hub and spoke networks” (Doctoral dissertation, Massachusetts Institute of Technology). 2 Jacquillat, A. (2012). “A queuing model of airport congestion and policy implications at JFK and EWR” (Doctoral dissertation, Massachusetts Institute of Technology). 3Simaiakis, I., Sandberg, M., & Balakrishnan, H. (2014). “Dynamic Control of Airport Departures: Algorithm Development and Field Evaluation”. IEEE Trans. Intell. Transport. Syst. IEEE Transactions on Intelligent Transportation Systems'', 15(1),'' 285-295. doi:10.1109/tits.2013.2278484. IEEE xplore. 4 Czachórski, T. (2014). “Queueing Models for Performance Evaluation of Computer Networks—Transient State Analysis”. Springer Proceedings in Mathematics & Statistics Analytic Methods in Interdisciplinary Applications'', 51-80. doi:10.1007/978-3-319-12148-2_4 ''